//
// Description: 413. 等差数列划分
// Created by Loading on 2021/8/10.
//

#include <bits/stdc++.h>

using namespace std;

int numberOfArithmeticSlices(vector<int> &nums) {
    // 储存相邻两项的差值
    vector<int> sub;
    for (int i = 1; i < nums.size(); ++i) {
        sub.emplace_back(nums[i] - nums[i - 1]);
    }

    vector<int> dp(sub.size());
    for (int i = 1; i < sub.size(); ++i) {
        // 与前一项差值相等，代表与前一项可以组成等差数列
        if (sub[i] == sub[i - 1]) {
            dp[i] = dp[i - 1] + 1;
        }
    }

    return accumulate(dp.begin(), dp.end(), 0);

    // 优化空间
//    if (nums.size() < 3) {
//        return 0;
//    }
//
//    int d = nums[1] - nums[0];
//    int cnt = 0;
//    int res = 0;
//    for (int i = 2; i < nums.size(); ++i) {
//        if (nums[i] - nums[i - 1] == d) {
//            ++cnt;
//        } else {
//            d = nums[i] - nums[i - 1];
//            cnt = 0;
//        }
//        res += cnt;
//    }
//
//    return res;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 1, 2, 3, 4, 3, 4, 5, 2, 4, 5, 6, 4, 3, 2, 6, 7, 8, 9, 10};
    int res = numberOfArithmeticSlices(nums);
    cout << res << endl;
}